;;; priority-queue.ss  --  Jens Axel S?gaard

;;; PURPOSE

; This file implements priority queues on top of
; the heap library.

(module priority-queue mzscheme
  (provide (all-defined))
  
  (require (lib "plt-pretty-big-text.ss" "lang"))
  (require "heap.ss")
  (require "ordered.ss")

  ;;; PRIORITY QUEUES (WITH EXPLICIT PRIORITIES)
  
  (define-signature priority-queue^    
    (empty
     empty? 
     insert
     ;insert*
     merge
     find-min
     find-min-pri
     delete-min
     ))
  
  (define-syntax (use-priority-queue stx)
    (syntax-case stx ()
      [(_ pq-unit)
       (datum->syntax-object stx `(,#`define-values/invoke-unit/sig priority-queue^ ,#`pq-unit))]
      [(_ pq-unit prefix) 
       (datum->syntax-object stx `(,#`define-values/invoke-unit/sig priority-queue^ ,#`pq-unit ,#`prefix))]))
  
  ; instantiate-priority-queue : heap-unit ordered-unit -> compound-unit
  ;  return priority-queue-unit representeing a prioroty queue of alpha elements
  (define (instantiate-priority-queue heap@ alpha@)
    (define pri-alpha@ 
      (unit/sig ordered^
        (import (alpha : ordered^))
        (define (pri p) (car p))
        (define (elm= x y)  (alpha:elm=  (pri x) (pri y)))
        (define (elm< x y)  (alpha:elm<  (pri x) (pri y)))
        (define (elm<= x y) (alpha:elm<= (pri x) (pri y)))))
    (compound-unit/sig 
      (import)
      (link (ALPHA      : ordered^        (alpha@))
            (PRI-ALPHA  : ordered^        (pri-alpha@ ALPHA))
            (ALPHA-HEAP : heap^           (heap@ PRI-ALPHA))
            (ALPHA-PQ   : priority-queue^ (priority-queue@   ALPHA-HEAP)))
      (export (open ALPHA-PQ))))
  
  
  (define priority-queue@
    (unit/sig priority-queue^
      (import (heap : heap^))
      
      (define (pri p) (car p))
      (define (elm p) (cdr p))
      
      (define empty? heap:empty?)
      (define empty heap:empty)
      (define (find-min pq) 
        (elm (heap:find-min pq)))    
      (define (find-min-pri pq)
        (pri (heap:find-min pq)))
      (define (insert pq x p)
        (heap:insert pq (cons p x)))
      ; two alternatives: 
      ;  1. (insert* pq l pri)  insert all elements of l with same priority pri
      ;  2. (insert* pq (list (x1 pri1) ...)) 
      ;  (define (insert* pq lst)
      ;    (foldl (lambda (elm acc) (insert acc (first elm) (second elm)))))
      (define delete-min heap:delete-min)
      (define merge heap:merge))))
